//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 
//
// 注意： 
//
// 
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 示例 3: 
//
// 
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 10⁵ 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 👍 1429 👎 0

package leetcode.editor.cn;

public class _76_MinimumWindowSubstring {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        Solution solution = new _76_MinimumWindowSubstring().new Solution();
        System.out.println(solution.minWindow(s, t));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {
            int sLen = s.length();
            int tLen = t.length();
            if (sLen == 0 || tLen == 0 || sLen < tLen) {
                return "";
            }

            char[] charArrayS = s.toCharArray();
            char[] charArrayT = t.toCharArray();

            int[] winFreq = new int[128];
            int[] tFreq = new int[128];

            for (char c : charArrayT) {
                tFreq[c]++;
            }

            int distance = 0;
            int minLen = sLen + 1; // 先设置一个达不到的长度
            int begin = 0;

            int left = 0;
            int right = 0;

            //[left, right)
            while (right < sLen) {
                if(tFreq[charArrayS[right]] == 0) {
                    right++;
                    continue;
                }

                if (winFreq[charArrayS[right]] < tFreq[charArrayS[right]]) {
                    distance++;
                }
                winFreq[charArrayS[right]]++;
                right++;

                while (distance == tLen) {

                    if (right - left < minLen){
                        minLen = right - left;
                        begin = left;
                    }

                    if(tFreq[charArrayS[left]] == 0) {
                        left++;
                        continue;
                    }

                    if (winFreq[charArrayS[left]] == tFreq[charArrayS[left]]) {
                        distance--;
                    }
                    winFreq[charArrayS[left]]--;
                    left++;
                }

            }
            if (minLen == sLen + 1) {
                return "";
            }
            return s.substring(begin, begin + minLen);
        }

        /**
         * 暴力解法
         *
         * @param s
         * @param t
         * @return
         */
        public String minWindow_baoli(String s, String t) {
            int slen = s.length();
            int tlen = t.length();
            int maxlen = slen;
            String res = "";
            for (int i = 0; i < slen; i++) {
                for (int j = i + tlen; j <= slen; j++) {
                    String tmp = s.substring(i, j);
                    if (isContains(tmp, t) && tmp.length() <= maxlen) {
                        res = tmp;
                        maxlen = res.length();
                    }
                }
            }
            return res;
        }

        private boolean isContains(String s, String t) {
            int[] sCount = lookCount(s);
            int[] tCount = lookCount(t);
            for (int i = 0; i < sCount.length; i++) {
                if (tCount[i] > sCount[i]) {
                    return false;
                }
            }
            return true;
        }

        private int[] lookCount(String s) {
            int[] res = new int[52];
            for (char ch : s.toCharArray()) {
                if (ch >= 'A' && ch <= 'Z') {
                    res[ch - 'A']++;
                } else {
                    res[ch - 'a' + 26]++;
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}